package gitdemo1.git3.day;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;

public class Manacher {
    public static void main(String[] args) {
        int i=manacher("ahhcchh");
        System.out.println(i);

    }
    public static int manacher(String s1){
        if(s1.length()<1||s1==null){
            return 0;
        }
        char[] chs = s1.toCharArray();
        char[] str = manacherString(s1);
        int R=-1;//最右边的长度还下一个
        int C=-1;//中心点
        //半径数组
        int arr[]=new int[str.length];
        int max=Integer.MIN_VALUE;//最长的半径
        int flag=0;

        for (int i = 0; i < str.length; i++) {
            arr[i]=i<R? Math.min(arr[C*2-i] , R-i) :1;
            while(i+arr[i]<str.length&&i-arr[i]>-1){
                if(str[i+arr[i]]==str[i-arr[i]]){
                    arr[i]++;
                }else{
                    break;
                }
            }
            if(i+arr[i]>R){
                R=i+arr[i];
                C=i;
            }
            max=Math.max(max, arr[i]);
//            if(arr[i]>max){
//                max=arr[i];
//                flag=i;
//            }

        }
//        for (int j = (flag-1)/2; j <=max; j++) {
//            System.out.print(chs[j]);
//
//        }
        System.out.println(str[flag+1]);
        System.out.println(str[flag]);
        System.out.println(str[flag-1]);

        return max-1;

    }

    private static char[] manacherString(String str) {
        char[] chs = str.toCharArray();
        char []newChs=new char[chs.length*2+1 ];
        int index=0;
        for (int i = 0; i < newChs.length; i++) {
            newChs[i]=i%2==0? '#': chs[index++];
        }

        return newChs;
    }


}

